package com.bigshen.algorithm.jBfs.solution02NWordLadder;

import java.util.*;

/**
 * 127. Word Ladder 单词接龙
 * Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
 *
 * Only one letter can be changed at a time.
 * Each transformed word must exist in the word list.
 * Note:
 *
 * Return 0 if there is no such transformation sequence.
 * All words have the same length.
 * All words contain only lowercase alphabetic characters.
 * You may assume no duplicates in the word list.
 * You may assume beginWord and endWord are non-empty and are not the same.
 *
 * Example 1:
 * Input:
 * beginWord = "hit",
 * endWord = "cog",
 * wordList = ["hot","dot","dog","lot","log","cog"]
 *
 * Output: 5
 *
 * Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
 * return its length 5.
 *
 * Example 2:
 *
 * Input:
 * beginWord = "hit"
 * endWord = "cog"
 * wordList = ["hot","dot","dog","lot","log"]
 *
 * Output: 0
 *
 * Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-ladder
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (null == wordList || wordList.size() == 0 || !wordList.contains(endWord)) {
            return 0;
        }
        int step = 1;
        Set<String> dict = new HashSet(wordList);
        Queue<String> queue = new LinkedList();
        Set<String> used = new HashSet();
        queue.offer(beginWord);
        used.add(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; i ++) {
                String currentWord = queue.poll();
                // 根据当前单词，获取下一批次单词
                List<String> nextWords = getNextUnUsedWords(currentWord, used, dict);
                for (int j = 0; j < nextWords.size(); j ++) {
                    if (endWord.equals(nextWords.get(j))) {
                        return step;
                    }
                    queue.offer(nextWords.get(j));
                }
            }

        }
        return 0;
    }

    private List<String> getNextUnUsedWords(String word, Set<String> used, Set<String> dict) {
        List<String> nextWords = new ArrayList();
        for (int i = 0; i < word.length(); i ++) {
            for (char j = 'a'; j <= 'z'; j ++) {
                char[] array = word.toCharArray();
                array[i] = j;
                String nextWord = new String(array);
                if (dict.contains(nextWord) && !used.contains(nextWord)) {
                    // 属于字典中单词，且没被使用过
                    used.add(nextWord);
                    nextWords.add(nextWord);
                }
            }
        }
        return nextWords;
    }



}
